package snippet;
import java.util.*;
public class 组合总和Ⅲ {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {

    	backtracking(k, n, 1);
//    	System.out.println(result);
    	return result;
    }
    public void backtracking(int k, int n, int index) {
    	// k个数 和为n
    	if(item.size() == k) {
    		if(sum == n) {
    			result.add(new ArrayList<>(item));
    		}
    		return;
    	}
    	
    	for(int i = index; i <= 9; i++) {
    		item.add(i);
    		sum += i;
    		backtracking(k, n, i + 1);
    		sum -= i;
    		item.remove(item.size() - 1);
    	}
    	
    }
    
    public static void main(String[] args) {
		new 组合总和Ⅲ() .combinationSum3(3, 9);
	}
}
